package main.堆;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author tmh
 * @date 2024/7/26 19:35
 * @description
 */
public class T347前K个高频元素 {

    /**
     * 使用优先级队列，优先级队列的底层是堆
     *
     * @param nums
     * @param k
     * @return
     */
    public int[] topKFrequent1(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            Integer value = map.getOrDefault(num, 0);
            map.put(num, value + 1);
        }
        //初始化优先级队列，根据value的值进行升序排序
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                //让priorityQueue根据map中value的大小来进行排序--》升序
                return map.get(o1)-map.get(o2);
            }
        });
        for (Integer key : map.keySet()) {
            if (queue.size() < k) {
                queue.add(key);
                //下面这个peek()得到的就是目前队列里面value值最小的key
            }else if (map.get(key)>map.get(queue.peek())){
                queue.remove();
                queue.add(key);
            }
        }
        //取出优先级队列里面的元素
        int[] res = new int[k];
        int index =0;
        while (!queue.isEmpty()){
            res[index++]=queue.remove();
        }
        return res;
    }


    /**
     * 暴力解法
     *
     * @param nums
     * @param k
     * @return
     */
    public int[] topKFrequent(int[] nums, int k) {
        int[] result = new int[k];
        // key : 数字; value ：出现到频次
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int curNum = nums[i];
            map.put(curNum, map.getOrDefault(curNum, 0) + 1);
        }

        // 根据 value 进行排序
        ArrayList<Map.Entry<Integer, Integer>> list = new ArrayList(map.entrySet());
        Collections.sort(list, (a, b) -> {
            return b.getValue() - a.getValue();
        });

        for (int i = 0; i < k; i++) {
            result[i] = list.get(i).getKey();
        }

        return result;
    }
}
